1. Field of the Invention
The present invention relates to the process of managing memory in a computer system. More specifically, the present invention relates to a method and an apparatus for freeing memory within a computing device, such as a smart card, which includes both volatile and non-volatile memory.
2. Related Art
Dramatic advances in computer technology presently make it possible to integrate a significant amount of computing power onto a xe2x80x9csmart cardxe2x80x9d. This increased computing power enables smart cards to support large numbers of applications. However, unlike conventional computing systems, smart card-based computing systems do not presently provide a mechanism for reclaiming memory occupied by objects that are no longer in use. This process of reclaiming unused memory is often referred to as xe2x80x9cgarbage collectionxe2x80x9d.
Garbage collection can be performed in conventional computing systems using a number of well-known techniques. However, smart card-based computing systems are different than conventional computing systems because objects can reside in writeable non-volatile memory, such as electrically erasable programmable read only memory (EEPROM) or flash memory. (Within this specification the term xe2x80x9cEEPROMxe2x80x9d refers to both xe2x80x9cEEPROMxe2x80x9d and xe2x80x9cflash memory.xe2x80x9d)
Existing garbage collection techniques are not suitable for EEPROM because individual memory elements in EEPROM can only be written to a limited number of times. Hence, existing garbage collection techniques, which operate by frequently marking objects in memory, can dramatically reduce the life expectancy of EEPROM. Moreover, the process of performing write operations to EEPROM is typically very slow, which can significantly degrade system performance.
Smart cards often contain a small amount of volatile random access memory (RAM), which does not suffer from the above-described problems of writeable non-nonvolatile memory. However, the amount of RAM is often extremely limited. Hence, it is not possible to store a complete image of EEPROM in RAM; even a bitmap representing blocks of EEPROM would take up too much space in RAM.
The garbage collection process operates by first deleting unused objects from memory. Once the objects are deleted, the memory space formerly occupied by the objects must somehow be reclaimed. In conventional computing systems, this reclamation process is typically accomplished by performing a compaction operation to eliminate xe2x80x9cholesxe2x80x9d in memory that arise as a consequence of deleting objects. However, a compaction operation typically involves rewriting a significant portion of memory, which tends to reduce the life expectancy of the EEPROM.
Hence, what is needed is a method and an apparatus for reclaiming memory without requiring the large number of write operations involved in performing a compaction operation.
Furthermore, in computing devices that include both EEPROM and RAM, it is possible to define xe2x80x9ctransient objects,xe2x80x9d which include a portion defined in EEPROM and a portion defined in RAM. In order to support such hybrid objects, what is needed is a method and an apparatus that reclaims memory used by these hybrid objects.
One embodiment of the present invention provides a system for freeing memory within a computing device. During operation, the system receives a command to free a given segment of memory within the computing device, wherein the command specifies the location of the given segment and the size of the given segment. In response to the command, the system adds the given segment to a free segment table that contains entries for free segments of memory within the computing device. During this process, if the given segment is contiguous with an existing segment in the free segment table, the given segment is concatenated with the existing segment by adding the given segment to an entry for the existing segment in the free segment table.
In a variation on this embodiment, if the given segment is not contiguous with any existing segments in the free segment table, adding the given segment to the free segment table involves adding a new entry for the given segment to the free segment table.
In a variation on this embodiment, if the free segment table is full and the given segment cannot be added to an existing entry in the free segment table, adding the given segment to the free segment table involves allocating an additional free segment table to accommodate the given segment.
In a variation on this embodiment, if the given segment is contiguous with two existing segments in the free segment table, so that the given segment bridges the two existing segments, the system concatenates the given segment and the two existing segments into a single segment and updates the free segment table accordingly.
In a variation on this embodiment, the system additionally allocates a new segment from the free segment table using a xe2x80x9cbest fitxe2x80x9d technique that allocates the smallest segment that is large enough to accommodate the new segment.
In a variation on this embodiment, prior to freeing the given segment, the system deletes an object that occupying the given segment.
In a variation on this embodiment, the memory within the computing device includes writeable non-volatile memory that can only be written to a limited number of times, and is hence not suited for a memory management system that performs compaction because of the large number of write operations involved in a compaction operation.
In a variation on this embodiment, the computing device can be located within a smart card that can be part of, an identification card, a client loyalty card, or an electronic wallet; or can be located within a cellular telephone.